package com.mlamp.其他;

import java.util.ArrayDeque;
import java.util.Calendar;
import java.util.Deque;
import java.util.Stack;

public class 最长有效扩号 {

    public static void main(String[] args) {
        String s = ")()()";
        最长有效扩号 instance = new 最长有效扩号();
        int i = instance.longestValidParentheses3(s);
        System.out.println(i);
        i = instance.lstValidParentheseC(s);
        System.out.println(i);
    }

    public int longestValidParentheses(String s) {
        int res = 0;
        if (s == null || s.length() == 0) return 0;
        char[] chars = s.toCharArray();
        int dp[] = new int[chars.length];
        for (int i = 1; i < chars.length; i++) {
            if (chars[i] == ')')
                if (chars[i - 1] == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && chars[i - dp[i - 1] - 1] == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
            res = Math.max(res, dp[i]);

        }
        return res;

    }


    public int longestValidParentheses3(String s) {
        int res = 0;
        if (s == null || s.isEmpty()) return 0;
        char[] chars = s.toCharArray();
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (chars[i] == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    res = Math.max(res, i - stack.peek());
                }
            }
        }
        return res;
    }


    public int longestValidParentheses5(String input) {
        if (input == null || input.isEmpty()) return 0;
        int res = 0;
        char[] inputs = input.toCharArray();
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);
        for (int i = 0; i < inputs.length; i++) {
            if (inputs[i] == '(') stack.push(i);
            else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    res = Math.max(res, i - stack.peek());
                }
            }
        }
        return res;
    }

    public int lgstValidParenthese5(String s) {
        int res = 0;
        if (s == null || s.isEmpty()) return res;
        char[] inputs = s.toCharArray();
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);
        for (int i = 0; i < inputs.length; i++) {
            if (inputs[i] == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    res = Math.max(res, i - stack.peek());
                }
            }
        }
        return res;
    }

    public int longestValidParentheses4(String s) {
        int res = 0;
        if (s == null || s.isEmpty()) return 0;
        char[] inputs = s.toCharArray();
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);
        for (int i = 0; i < inputs.length; i++) {
            if (inputs[i] == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    res = Math.max(res, i - stack.peek());
                }
            }
        }
        return res;
    }


    public int longestValidParenthese3(String s) {
        int res = 0;
        if (s == null || s.isEmpty()) return 0;
        char[] inputs = s.toCharArray();
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);
        for (int i = 0; i < inputs.length; i++) {
            if (inputs[i] == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    res = Math.max(res, i - stack.peek());
                }
            }
        }
        return res;
    }


    public int longestValidParentheses2(String s) {
        int res = 0;
        if (s == null || s.length() == 0) return 0;
        char[] chars = s.toCharArray();
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    res = Math.max(res, i - stack.peek());
                }
            }
        }
        return res;
    }

    public int longestValidParenthesesA(String s) {
        if (s == null || s.length() == 0) throw new IllegalArgumentException("invalid string given");
        int res = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);
        char[] nums = s.toCharArray();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == '(') stack.push(i);
            else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    res = Math.max(res, i - stack.peek());
                }
            }
        }
        return res;
    }


    public int lstValidParentheseC(String c) {
        assert c != null : "c can not be null";
        assert c.length() > 0 : "c can be empty";
        int res = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);
        char[] arrays = c.toCharArray();
        for (int i = 0; i < arrays.length; i++) {
            if (arrays[i] == '(') stack.push(i);
            else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    res = Math.max(res, i - stack.peek());
                }
            }
        }
        return res;
    }


    public int lstValidParrentheseB(String s) {
        if (s == null || s.trim().length() == 0) throw new IllegalArgumentException("invalid string given");
        int res = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);
        char[] arrays = s.toCharArray();
        for (int i = 0; i < arrays.length; i++) {
            if (arrays[i] == '(') stack.push(i);
            else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    res = Math.max(res, i - stack.peek());
                }
            }
        }
        return res;
    }
}
